package com.wxit.algorithm.heap;

/**
 * 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 解题思路：
 *  1. 向小顶堆放入前k个元素
 *  2.剩余元素
 *      若 《= 堆顶元素，则忽略
 *      若 > 堆顶元素，则替换
 *  3.这样小顶堆始终保持的是到目前位置为止前k大的元素
 *  4.循环结束后，堆顶元素即为第k大的数
 */
public class LeetCode215 {

    public int findKthLargest(int[] nums, int k) {
        MinHeap heap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {
                heap.replace(nums[i]);
            }
        }
        return heap.peek();
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode215().findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
    }
}
